/*
 *  复习一下二叉树的前中后层序遍历
 * */

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


class Solution {
public:
    // 前 递归法
    void preorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }
        res.push_back(root->val);
        preorder(root->left, res);
        preorder(root->right, res);
    }

    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }

    // 前 迭代法
    vector<int> preorderTraversal2(TreeNode *root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        stack<TreeNode *> s;
        TreeNode *node = root;
        while (!s.empty() || node != nullptr) {
            while (node != nullptr) {
                res.emplace_back(node->val);
                s.emplace(node);
                node = node->left;
            }
            node = s.top();
            s.pop();
            node = node->right;
        }
        return res;
    }

    // 前 Morris遍历
    vector<int> preorderTraversal3(TreeNode *root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        TreeNode *p1 = root, *p2 = nullptr;
        while (p1 != nullptr) {
            p2 = p1->left;
            if (p2 != nullptr) {
                while (p2->right != nullptr && p2->right != p1) {
                    p2 = p2->right;
                }
                // 其实这里就用到了回溯了
                if (p2->right == nullptr) {
                    res.emplace_back(p1->val);
                    p2->right = p1;
                    p1 = p1->left;
                    continue;
                } else {
                    // 该回溯了
                    p2->right = nullptr;
                }
            } else {
                res.emplace_back(p1->val);
            }
            p1 = p1->right;
        }
        return res;
    }

    // 中 递归法
    void inorder(TreeNode *root, vector<int>& res) {
        if (!root) {
            return;
        }
        inorder(root->left, res);
        res.emplace_back(root->val);
        inorder(root->right, res);
    }

    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> res;
        inorder(root, res);
        return res;
    }

    // 中 迭代法
    vector<int> inorderTraversal2(TreeNode *root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        stack<TreeNode *> s;
        while (root != nullptr || !s.empty()) {
            while (root != nullptr) {
                s.push(root);
                root = root->left;
            }
            root = s.top();
            s.pop();
            res.push_back(root->val);
            root = root->right;
        }
        return res;
    }

    // 中 Morris遍历
    vector<int> inorderTraversal3(TreeNode *root) {
        vector<int> res;
        TreeNode *prev = nullptr;
        while (root != nullptr) {
            prev = root->left;
            if (prev != nullptr) {
                while (prev->right != nullptr && prev->right != root) {
                    prev = prev->right;
                }
                if (prev->right == nullptr) {
                    prev->right = root;
                    root = root->left;
                } else {
                    // 说明左子树已经遍历过
                    res.emplace_back(root->val);
                    root = root->right;
                }
            } else {
                // 左边没有树了
                res.emplace_back(root->val);
                root = root->right;
            }
        }
        return res;
    }

    // 后 递归法
    void postorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }
        postorder(root->left, res);
        postorder(root->right, res);
        res.emplace_back(root->val);
    }

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        postorder(root, res);
        return res;
    }

    // 后 迭代法
    vector<int> postorderTraversal2(TreeNode *root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        stack<TreeNode *> s;
        TreeNode *prev = nullptr;
        while (root != nullptr || !s.empty()) {
            while (root != nullptr) {
                s.emplace(root);
                root = root->left;
            }
            root = s.top();
            s.pop();
            // 这里也用到了回溯 但是我之前在这里犯了一个误区，完全是我对内存的认识不深刻
            // 之前认为prev就没必要，其实它只是让root这个指针置空，但是它原先指向的那块是一直存在的
            if (root->right == nullptr || root -> right == prev) {
                res.emplace_back(root->val);
                prev = root;
                root = nullptr;
            } else {
                s.emplace(root);
                root = root->right;
            }
        }
        return res;
    }

    // 后 Morris遍历
    void addPath(TreeNode *root, vector<int>& res) {
        int count = 0;

        while (root != nullptr) {
            ++count;
            res.emplace_back(root->val);
            root = root->right;
        }
        reverse(res.end() - count, res.end());
    }

    vector<int> postorderTraversal3(TreeNode *root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        TreeNode *node = root, *prev = nullptr;
        while (node != nullptr) {
            prev = node->left;
            if (prev != nullptr) {
                while (prev->right != nullptr && prev->right != node) {
                    prev = prev->right;
                }

                if (prev->right == nullptr) {
                    prev->right = node;
                    node = node->left;
                    continue;
                } else {
                    // 说明左子树已经遍历过
                    prev->right = nullptr;
                    addPath(node->left, res);
                }
            }
            node = node->right;
        }
        // 执行到这说明所有的左子树都已经遍历完毕，只剩从根开始往右子树上的一条线
        addPath(root, res);

        return res;
    }
};

int main() {


    return 0;
}